<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>2.4.- flat_stable_sort</title>
<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Boost.Sort">
<link rel="up" href="../single_thread.html" title="2.- Single Thread Algorithms">
<link rel="prev" href="spinsort/spinsort_programming.html" title="Programming">
<link rel="next" href="flat_stable_sort/flat_stable_sort_benchmark.html" title="Benchmark">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="spinsort/spinsort_programming.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../single_thread.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="flat_stable_sort/flat_stable_sort_benchmark.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="sort.single_thread.flat_stable_sort"></a><a class="link" href="flat_stable_sort.html" title="2.4.- flat_stable_sort">2.4.- flat_stable_sort</a>
</h3></div></div></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="sort.single_thread.flat_stable_sort.flat_stable_sort_description"></a><a class="link" href="flat_stable_sort.html#sort.single_thread.flat_stable_sort.flat_stable_sort_description" title="Description">Description</a>
</h4></div></div></div>
<div class="blockquote"><blockquote class="blockquote">
<p>
            <span class="bold"><strong>Flat_stable_sort</strong></span> is a new stable sort
            algorithm, designed and implemented by Francisco Jose Tapia for the Boost
            Sort Library
          </p>
<p>
            The goal of the algorithm is to stably sort with little additional memory
            (about 1% of the memory used by the data).
          </p>
<p>
            The default stable sort algorithms provided by most compilers and libraries
            use substantial additional memory, usually half of the data to sort.
          </p>
<p>
            This new algorithm provides around 80%-90% of the speed of the spinsort
            and the stable sort algorithms provided by compilers and libraries.
          </p>
<p>
            This algorithm is fast when the data is almost sorted. Many times the
            new elements are inserted at the end of the sorted elements, or some
            elements are modified, breaking the order of the elements. In these cases,
            the flat_stable_sort algorithm is very fast.
          </p>
<p>
            <span class="bold"><strong>
<pre class="programlisting">                 |         |                             |                                |
Algorithm        | Stable  |      Additional Memory      | Best, average, and worst case  |
-----------------+---------+-----------------------------+--------------------------------+
flat_stable_sort |   Yes   | size of the data / 256 + 8K |     N, NlogN , NlogN           |
                 |         |                             |                                |
</pre>
            </strong></span>
          </p>
</blockquote></div>
<div class="blockquote"><blockquote class="blockquote">
<h5>
<a name="sort.single_thread.flat_stable_sort.flat_stable_sort_description.h0"></a>
            <span class="phrase"><a name="sort.single_thread.flat_stable_sort.flat_stable_sort_description.memory_used"></a></span><a class="link" href="flat_stable_sort.html#sort.single_thread.flat_stable_sort.flat_stable_sort_description.memory_used"><span class="underline">Memory Used</span></a>
          </h5>
<p>
            Memory used by the stable sort algorithms measured on Linux x64
          </p>
<p>
            <span class="bold"><strong>
<pre class="programlisting">   Algorithm       | Memory used  |
-------------------+--------------+
std::stable_sort   |   1177 MB    |
spinsort           |   1175 MB    |
flat_stable_sort   |    788 MB    |
-------------------+--------------+
</pre>
            </strong></span>
          </p>
</blockquote></div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2014-2017 Steven
      Ross, Francisco Tapia, Orson Peters<p>
        Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
        Software License, Version 1.0</a>.
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="spinsort/spinsort_programming.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../single_thread.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="flat_stable_sort/flat_stable_sort_benchmark.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
